package ejercicio1;

import java.util.ArrayList;

 public class Ejercicio1 {

 static ArrayList mejorCamino=new ArrayList();
 static final int N = 5; //Filas
 static final int M = 7; //Columnas
 static int tablero[][]={
{ 2,  5, 1,-4,  2,-5, 1},
{ 3, -1,-3, 2, -4, 3,-7},
{ 4,  2,-1,-1, -3,-2, 1},
{ 3,  1,-2, 4 ,-3,-8, 6},
{-4,-50, 6, 2 ,-3, 3, 0}
};
static int vi[]={1,1,0,-1,-1,-1, 0, 1};
static int vj[]={0,1,1, 1, 0,-1,-1,-1};

public static void main(String[] args) {
 Ejercicio1 ej = new Ejercicio1();
 Ejercicio1.visualizaLaberinto(tablero);
 System.out.println();
 Camino unCamino=new Camino();
 unCamino.recorrido=copioTablero(tablero);
ej.caminos(-1,0,N-1,M-1,0,0,15,new Entero(0),unCamino,tablero);
Ejercicio1.imprimirSoluciones(mejorCamino);
}

//Pre: La energia del campo solo puede ser 0 en el campo NxM.
//Pos: El algoritmo despliega el tablero original, seguido de los tableros con mayor
//nivel de energia, y cantidad de pasos menor que la maxima cantidad de pasos.
public void caminos(int iOrigen, int jOrigen, int iDestino, int jDestino, int nivelDeEnergiaActual,
	int numPasos, int maxPasos,Entero mejorNivelDeEnergia, Camino caminoActual, int mapa[][]){
    int i,j,energiaPos;
    for(int pos=0;pos<8;pos++){                                         //para todos los candidatos
        i=iOrigen+vi[pos];
	j=jOrigen+vj[pos];                                              //seleccionar candidato
	if(perteneceAlCamino(i,j)&&!pase(i,j,caminoActual.recorrido)&&numPasos<maxPasos){
            energiaPos=mapa[i][j];
            if(nivelDeEnergiaActual+energiaPos>0){                      //si es aceptable
                caminoActual.recorrido[i][j]=0;                         //anoto candidato
		nivelDeEnergiaActual+=mapa[i][j];
		numPasos+=1;
		if(i!=iDestino||j!=jDestino){                           //si solucion incompleta
                    Camino unCamino=new Camino();
                    unCamino.recorrido=copioTablero(caminoActual.recorrido);
                    caminos(i,j,iDestino,jDestino,nivelDeEnergiaActual,numPasos,maxPasos,mejorNivelDeEnergia,unCamino,mapa);
    		}else{
                    if(nivelDeEnergiaActual>mejorNivelDeEnergia.valor){
                        mejorCamino.clear();
                        agregoSolucion(caminoActual);                   //anoto solucion
			mejorNivelDeEnergia.valor=nivelDeEnergiaActual;
                    }else if(nivelDeEnergiaActual==mejorNivelDeEnergia.valor)
			agregoSolucion(caminoActual);                   //anoto solucion
		}
		caminoActual.recorrido[i][j]=mapa[i][j];                //borro candidato
		if(!(i==0&&j==0)){                                      //Fix para posicion inicial
                nivelDeEnergiaActual-=mapa[i][j];
                numPasos=numPasos-1;
                }
            }
	}
    }
}
/*
 * procedimiento ensayar (paso: TipoPaso)
     para cada candidato hacer
          seleccionar candidato
          if aceptable then  
               anotar_candidato
             if solucion_incompleta then
                 ensayar(paso_siguiente)    
             else 
                 almacenar_solucion
          borrar_candidato 
    hasta que candidatos_agotados
  fin procedimiento

 */


public static void visualizaLaberinto(int[][]unTablero) {
 for (int i = 0; i < N; ++i) {
  for (int j = 0; j < M; ++j) {
      if(unTablero[i][j]>=0&&unTablero[i][j]<10)
           System.out.print(" ");
      System.out.print(unTablero[i][j]+ " ");

  }
 System.out.println();
 }

}

//Pre: recibe 2 valores i,j de un tablero
//Pos: retorna true si pertenece al tablero, fase si no pertenece.
public static boolean perteneceAlCamino(int i,int j){
 return(i>=0 && i<N && j>=0 && j<M);
}

//Pre: recibe 2 valores i,j de un tablero y un Camino
//Pos: retorna true si ya se paso por ese punto en el Camino, false si no.
public boolean pase(int i,int j,int[][] camino){
if(i==N-1&&j==M-1)
    return false;
else
    return camino[i][j]==0;

}

//Pre: recibe un tablero
//Pos: retorna un nuevo tablero, con los mismos datos que el recibido por parametro.
private static int [][] copioTablero(int[][]unTablero){
    int retorno[][]=new int[N][M];
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
        retorno[i][j]=unTablero[i][j];
        }
    }
    return retorno;
}

//Pre: recibe una ArrayList de Caminos.
//Pos: imprime en pantalla dichos Caminos.
    public static void imprimirSoluciones(ArrayList mejoresCaminos) {
       for(int i=0;i<mejoresCaminos.size();i++){
           Camino unCamino=(Camino) mejoresCaminos.get(i);
           visualizaLaberinto(unCamino.recorrido);
           System.out.println();
           System.out.println();
       }

    }

    //Pre: recibe un Camino.
    //Pos: lo agrega a la lista de mejores caminos.
    private void agregoSolucion(Camino caminoActual) {
        Camino unCamino=new Camino();
        unCamino.recorrido=copioTablero(caminoActual.recorrido);
        mejorCamino.add(unCamino);
    }

  

}